public class TestOJ {
    static class TreeNode{
        public char val;//数据域
        public TreeNode left;//左孩子引用
        public TreeNode right;//右孩子引用

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root;//根节点

    //判断两棵树是否相同
    public boolean isSameTree(TreeNode p,TreeNode q){
        if (p == null && q == null){
            return true;
        }
        if ((p == null && q != null) ||(p != null && q == null)){
            return false;
        }
        if (p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    //判断一棵树是否为另一棵树的子树
    public boolean isSubTree(TreeNode root,TreeNode subRoot){
        if (root == null || subRoot == null){
            return false;
        }
        if (isSameTree(root,subRoot)){//该树可能与子树相同
            return true;
        }
        if (isSameTree(root.left,subRoot)){//该树的左子树可能与子树相同
            return true;
        }
        if (isSameTree(root.right,subRoot)){//该树的右子树可能与子树相同
            return true;
        }
        return false;
    }
    //翻转二叉树并返回其根节点
    public TreeNode invertTree(TreeNode root){
        if (root == null){
            return null;
        }

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    //判断一棵二叉树是否为平衡二叉树
/*    public boolean isBalanced(TreeNode root){
        if (root == null){
            return true;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.abs(leftH - rightH) < 2
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
    public int getHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHight = getHeight(root.left);
        int rightHight = getHeight(root.right);
        return ((leftHight>rightHight) ? (leftHight+1) : (rightHight+1));
    }*/
    //时间复杂度更小的方法
    public boolean isBalanced(TreeNode root){
        return getHeight(root) >= 0;
    }
    public int getHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHight = getHeight(root.left);
        int rightHight = getHeight(root.right);
        //如果左右子树平衡就返回该结点处子树的高度（该结点左右子树中最大高度）
        //否则就返回-1
        if (leftHight >= 0 && rightHight >= 0 &&
        Math.abs(leftHight - rightHight)<=1){
            //如果这棵树没有右子树的话，左子树返回-1（不平衡），右子树高度为0
            //绝对值为1。这种情况会被误认为是平衡二叉树而出现返回值影响结果
            //所以限制左右高度大于0
            return Math.max(leftHight,rightHight)+1;
        }else {
            return -1;
        }
    }
    //对称二叉树
    public boolean isSymmetric(TreeNode root){
        if (root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if (leftTree != null && rightTree == null || leftTree == null
        && rightTree != null){
            return false;
        }
        if (leftTree == null && rightTree == null){
            return true;
        }
        if (leftTree.val != rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                && isSymmetricChild(leftTree.right,rightTree.left);
    }
}
